Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Maximum Score of a Good Subarray

Problem Statement

Given an array of positive integers nums (0-indexed) and an integer k, return the maximum possible score of a good subarray.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). If any subarray follows i <= k <= j condition, it is considered as good subarray.

Examples

Example 1:

  • Input: nums = [1, 2, 3, 4, 5], k = 2
  • Expected Output: 9
  • Justification: The best subarray is [3, 4, 5], where the minimum value is 3, and the length is 3. The score is 3 * 3 = 9.

Example 2:

  • Input: nums = [8, 1, 2, 4, 3], k = 3
  • Expected Output: 6
  • Justification: The best subarray is [2, 4, 3], where the minimum value is 2, and the length is 3. The score is 2 * 3 = 6.

Example 3:

  • Input: nums = [4, 6, 4, 7, 2, 5, 1], k = 4
  • Expected Output: 12
  • Justification: The optimal subarray is [4, 6, 4, 7, 2, 5], with the minimum value 2 and length 6. Therefore, the score is 2 * 6 = 12.

Solution

To solve this problem, we start by considering the element at index k as the initial "good" subarray. Since the minimum value of a subarray containing only one element is the element itself, and the length is 1, the initial score is the value of nums[k]. We then expand this subarray to include adjacent elements on either side, continuously updating our calculation of the minimum value in the expanded subarray and its length. This process continues as long as expanding the subarray increases the score.

The key to this approach is to utilize a two-pointer technique, where we start with both pointers at k and expand outwards, ensuring that we always include k in our subarray. This ensures that all potential "good" subarrays are considered. The reason this method is effective is that it directly targets the constraint that k must always be within the subarray, allowing us to efficiently explore all relevant options without unnecessary comparisons or calculations.

Step-by-Step Algorithm

  1. Initialize pointers and variables:

    • Start with two pointers left and right at the index k. This marks the beginning of the subarray to consider.
    • Initialize minVal to the value at index k in nums, since this is the only element in the current subarray.
    • Set maxScore also to the value at index k, as this is the score of the subarray consisting of only the kth element.
  2. Expand the subarray:

    • Use a loop to expand the subarray to the left and right, as long as there are elements to consider (i.e., left > 0 or right < nums.length - 1).
    • Determine whether to move left or right based on boundary conditions and the values adjacent to the current subarray:
      • If left is at the start (0), only right can be moved.
      • If right is at the end (nums.length - 1), only left can be moved.
      • Otherwise, move the pointer (left or right) towards the side with the higher adjacent value to potentially increase the subarray's score.
  3. Update minimum value and score:

    • After each expansion, update minVal to the minimum value in the new subarray. This involves comparing minVal with the new elements included in the subarray.
    • Calculate the score of the current subarray (minVal * (right - left + 1)) and update maxScore if this new score is higher than the current maxScore.
  4. Repeat until fully expanded:

    • Continue expanding the subarray and updating the score until both left and right cannot be moved further (i.e., until the subarray spans the entire array).
  5. Return the maximum score found:

    • Once the loop completes, return maxScore as the maximum possible score of a "good" subarray.

Algorithm Walkthrough

Let's consider the INput: nums = [4, 6, 4, 7, 2, 5, 1], k = 4

  1. Initialization:

    • left = 4, right = 4, minVal = 2, maxScore = 2 (since nums[4] = 2).
  2. First Expansion:

    • Can move both left and right (since neither are at the array's ends).
    • nums[3] = 7 (left of left) is greater than nums[5] = 5 (right of right), so move left to 3.
    • Update minVal to min(2, 7) = 2.
    • New score is 2 * (4 - 3 + 1) = 4. Update maxScore to 4.
  3. Second Expansion:

    • Again, both left and right can move.
    • nums[2] = 4 (left of left) is less than nums[5] = 5, so move right to 5.
    • Update minVal to min(2, 5) = 2.
    • New score is 2 * (5 - 3 + 1) = 6. Update maxScore to 6.
  4. Third Expansion:

    • Both left and right can still move.
    • nums[1] = 6 (left of left) is greater than nums[6] = 1 (right of right), so move left to 2.
    • Update minVal to min(2, 4) = 2.
    • New score is 2 * (5 - 2 + 1) = 8. Update maxScore to 8.
  5. Fourth Expansion:

    • Both pointers can move.
    • nums[0] = 4 is greater than nums[6] = 1, so move left to 1.
    • Update minVal to min(2, 6) = 2.
    • New score is 2 * (5 - 1 + 1) = 10. Update maxScore to 10.
  6. Fifth Expansion:

    • left can move (to 0), but right cannot (already at the end).
    • Move left to 0.
    • Update minVal to min(2, 4) = 2.
    • New score is 2 * (5 - 0 + 1) = 12. Update maxScore to 12.
  7. Completion:

    • No further expansions are possible.
    • The loop ends, and the method returns maxScore = 12.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • The time complexity of the solution is , where n is the number of elements in the input array nums. This is because, in the worst case, the algorithm expands the search space to include each element of the array once as it attempts to find the maximum score.

Space Complexity:

  • The space complexity of the solution is , as the solution uses a fixed amount of additional space regardless of the input size. The extra space is used for the pointers and variables to store the current minimum value, current score, and maximum score found so far.
Maximum Score of a Good Subarray (hard)
Trapping Rain Water (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis